/*
 * Copyright 2011-2012 by The Regents of the University of California Licensed
 * under the Apache License, Version 2.0 (the "License"); you may not use this
 * file except in compliance with the License. you may obtain a copy of the
 * License from
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package edu.ucsd.db.bassarisk.query.expression.visitor;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

import edu.ucsd.db.bassarisk.exception.SchemaValidationException;
import edu.ucsd.db.bassarisk.exception.VisitorException;
import edu.ucsd.db.bassarisk.query.TransformReturn;
import edu.ucsd.db.bassarisk.query.ValidationTraversalLog;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanAnd;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanNot;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanOr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.Expression;
import edu.ucsd.db.bassarisk.query.expression.Expressions.KeywordMatchExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.NonterminalExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.PositionMaxSeparation;
import edu.ucsd.db.bassarisk.query.expression.Expressions.PositionMinSeparation;
import edu.ucsd.db.bassarisk.query.expression.Expressions.PositionOrdered;
import edu.ucsd.db.bassarisk.query.expression.Expressions.PositionPhrase;
import edu.ucsd.db.bassarisk.query.expression.Expressions.PositionPredExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.PositionSeparation;
import edu.ucsd.db.bassarisk.query.expression.Expressions.PositionWindow;
import edu.ucsd.db.bassarisk.query.expression.Expressions.StructureFind;
import edu.ucsd.db.bassarisk.query.expression.Expressions.StructureIn;
import edu.ucsd.db.bassarisk.query.expression.Expressions.StructurePredExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.StructureSame;
import edu.ucsd.db.bassarisk.schema.Schema;
import edu.ucsd.db.bassarisk.schema.Schema.SequenceRelationship;

/**
 * Visit each node in the query expression tree. The goal of this visitation is
 * to note at each structure-constraining expression what schema nodes it may
 * constrain. We are further interested in how those constraints interact with
 * constraints inherited from the parent/ancestor expression.
 * <p>
 * <h5>Limitations:</h5>
 * This traversal only reasons about containment between full classes of
 * structural nodes (according to run-class name) at each expression. It does
 * not consider how ancestor/descendant filter the subclasses. That additional
 * work is done when introducing bindings. This visitor can be seen as a
 * pre-filter to that visitor.
 * <p>
 * This visitation is a transformation that simplifies queries in several ways:
 * <ul>
 * <li>When the constraints added by a visited structure predicate expression
 * are already established by ancestor expressions, then the expression is
 * redundant and may be removed. <br/>
 * Ex: <code>Same:sentence(Same:sentence(a b)) ~~>
 * Same:sentence(a b)</code>
 * <li>When the constraints added by a visited position predicate are weaker
 * than the constraints placed by an ancestor expression, then the expression is
 * redundant and may be removed. <br/>
 * Ex: <code>Same:sentence(Window:3:sentence(a b)) ~~>
 * Same:sentence(a b)</code>
 * <li>PITFALL: Remember that our data-model is not XML. Two "sibling elements"
 * (sibling run-classes) may overlap in the position space. In XML, the values
 * at two paths <code>/document/title</code>, </code>/document/body</code> are
 * mutually exclusive. That is not true in our data-model, thus we consider the
 * complex relationships between structure classes defined in
 * {@link SequenceRelationship}.
 * </ul>
 */
public class StructurePredicateSimplificationTransformation
    implements
    ExpressionTreeVisitor<StructurePredicateSimplificationTransformation.Return, Void> {
  class Return implements TransformReturn<Expression> {
    private final Set<String> independantlyOver;
    private final Set<String> togetherOver;
    private final Expression transformed;

    private Return(final Expression transformed) {
      this.transformed = transformed;
      this.togetherOver = new HashSet<String>();
      this.independantlyOver = new HashSet<String>();
    }

    private Return(final Expression transformed, final Set<String> togetherOver,
                   final Set<String> independantlyOver) {
      this.transformed = transformed;
      this.togetherOver = togetherOver;
      this.independantlyOver = independantlyOver;
    }

    @Override
    public Expression getTransformationRoot() {
      return this.transformed;
    }
  }

  /**
   * At any point in the visitation traversal, the set of Strings in this stack
   * are the names of several classes of position runs. All positions matched to
   * sub expressions under this point in the visitation must fall under some
   * instance of each of these classes, though <i>different matching positions
   * may fall under different instances</i>.
   **/
  private final Stack<String> independantlyUnder;
  /**
   * A data structure representing the schema of the data this query is issued
   * against.
   */
  private final Schema schema;
  /**
   * At any point in the visitation traversal, the set of Strings in this stack
   * are the names of several classes of position runs. All positions matched to
   * sub expressions under this point in the visitation must fall under some
   * instance of each of these classes, <i>all positions under the same instance
   * for each class</i>.
   **/
  private final Stack<String> togetherUnder;
  private final ValidationTraversalLog vtl;

  public StructurePredicateSimplificationTransformation(final Schema schema,
                                                        final ValidationTraversalLog vtl) {
    this.schema = schema;
    this.vtl = vtl;
    this.togetherUnder = new Stack<String>();
    this.independantlyUnder = new Stack<String>();
  }

  /**
   * Checks a collection of existing containment constraints
   * (togetherConstraints) for any that subsume a new constraint (runClassName).
   */
  private boolean isTogetherUnder(final String runClassName,
                                  final Collection<String> togetherConstraints) {
    for (String runClassUnder : togetherConstraints) {
      if (runClassUnder.equals(runClassName)) { return true; }
      try {
        if (SequenceRelationship.AllContainedBy == this.schema
            .findSeqRelationship(runClassUnder, runClassName)) { return true; }
      } catch (SchemaValidationException e) {
        this.vtl.addError(e);
      }
    }
    return false;
  }

  @Override
  public Return visitBooleanAnd(final BooleanAnd expr, final Void arg)
      throws VisitorException {
    List<Expression> subExprs = new ArrayList<Expression>();
    Set<String> newIndependantOver = new HashSet<String>();
    boolean first = true;
    for (Expression subExpr : expr.getSubExprs()) {
      Return subReturn = subExpr.accept(this, null);
      subExprs.add(subReturn.transformed);
      if (first) {
        newIndependantOver.addAll(subReturn.togetherOver);
        newIndependantOver.addAll(subReturn.independantlyOver);
        first = false;
      } else {
        Set<String> combined = new HashSet<String>();
        combined.addAll(subReturn.togetherOver);
        combined.addAll(subReturn.independantlyOver);
        newIndependantOver.retainAll(combined);
      }
    }
    return new Return(expr.transform(subExprs), new HashSet<String>(),
                      newIndependantOver);
  }

  @Override
  public Return visitBooleanExpr(final BooleanExpr expr, final Void arg)
      throws VisitorException {
    throw VisitorException.requireSubclassImplementation();
  }

  @Override
  public Return visitBooleanNot(final BooleanNot expr, final Void arg)
      throws VisitorException {
    List<Expression> subExprs = new ArrayList<Expression>();
    subExprs.add(expr.getSubExpr().accept(this, null).transformed);
    return new Return(expr.transform(subExprs));
  }

  @Override
  public Return visitBooleanOr(final BooleanOr expr, final Void arg)
      throws VisitorException {
    List<Expression> subExprs = new ArrayList<Expression>();
    Set<String> newTogetherOver = new HashSet<String>();
    Set<String> newIndependantOver = new HashSet<String>();
    boolean first = true;
    for (Expression subExpr : expr.getSubExprs()) {
      Return subReturn = subExpr.accept(this, null);
      subExprs.add(subReturn.transformed);
      if (first) {
        newTogetherOver.addAll(subReturn.togetherOver);
        newIndependantOver.addAll(subReturn.togetherOver);
        newIndependantOver.addAll(subReturn.independantlyOver);
        first = false;
      } else {
        newTogetherOver.retainAll(subReturn.togetherOver);
        Set<String> combined = new HashSet<String>();
        combined.addAll(subReturn.togetherOver);
        combined.addAll(subReturn.independantlyOver);
        newIndependantOver.retainAll(combined);
      }
    }
    newIndependantOver.removeAll(newTogetherOver);
    return new Return(expr.transform(subExprs), newTogetherOver, newIndependantOver);
  }

  @Override
  public Return visitKeywordMatchExpr(final KeywordMatchExpr expr, final Void arg)
      throws VisitorException {
    return new Return(expr);
  }

  @Override
  public Return visitNonterminalExpr(final NonterminalExpr expr, final Void arg)
      throws VisitorException {
    throw VisitorException.requireSubclassImplementation();
  }

  @Override
  public Return visitPositionMaxSeparation(final PositionMaxSeparation expr,
                                           final Void arg) throws VisitorException {
    return this.visitStructureConstrainingPositionPredExpr(expr,
                                                           expr.getRunClassName());
  }

  @Override
  public Return visitPositionMinSeparation(final PositionMinSeparation expr,
                                           final Void arg) throws VisitorException {
    return this.visitStructureConstrainingPositionPredExpr(expr,
                                                           expr.getRunClassName());
  }

  @Override
  public Return visitPositionOrdered(final PositionOrdered expr, final Void arg)
      throws VisitorException {
    Return subReturn = expr.getSubExpr().accept(this, null);
    return new Return(subReturn.transformed, subReturn.togetherOver,
                      subReturn.independantlyOver);
  }

  @Override
  public Return visitPositionPhrase(final PositionPhrase expr, final Void arg)
      throws VisitorException {
    Return subReturn = expr.getSubExpr().accept(this, null);
    return new Return(subReturn.transformed, subReturn.togetherOver,
                      subReturn.independantlyOver);
  }

  @Override
  public Return visitPositionPredExpr(final PositionPredExpr expr, final Void arg)
      throws VisitorException {
    throw VisitorException.requireSubclassImplementation();
  }

  @Override
  public Return
      visitPositionSeparation(final PositionSeparation expr, final Void arg)
          throws VisitorException {
    return this.visitStructureConstrainingPositionPredExpr(expr,
                                                           expr.getRunClassName());
  }

  @Override
  public Return visitPositionWindow(final PositionWindow expr, final Void arg)
      throws VisitorException {
    return this.visitStructureConstrainingPositionPredExpr(expr,
                                                           expr.getRunClassName());
  }

  private Return
      visitStructureConstrainingPositionPredExpr(final PositionPredExpr expr,
                                                 final String runClassName)
          throws VisitorException {
    // This expression is redundant if constraints applied by outer
    // expressions subsume those added by this expression
    if (this.isTogetherUnder(runClassName, this.togetherUnder)) { //
      return expr.getSubExpr().accept(this, null);
    }
    Return subReturn = expr.getSubExpr().accept(this, null);
    // This expression may be eliminated if constraints applied by the
    // sub-expression subsume the constraints this expression adds.
    if (this.isTogetherUnder(runClassName, subReturn.togetherOver)) { //
      return subReturn;
    }
    subReturn.independantlyOver.add(runClassName);
    return new Return(expr.transform(subReturn.transformed), subReturn.togetherOver,
                      subReturn.independantlyOver);
  }

  @Override
  public Return visitStructureFind(final StructureFind expr, final Void arg)
      throws VisitorException {
    // Add the run-class constraint created by this expression to the
    // togetherUnder stack.
    this.togetherUnder.add(expr.getRunClassName());
    Return subReturn = expr.getSubExpr().accept(this, null);
    this.togetherUnder.pop();
    Return thisReturn =
        new Return(expr.transform(subReturn.transformed), subReturn.togetherOver,
                   subReturn.independantlyOver);
    thisReturn.togetherOver.add(expr.getRunClassName());
    return thisReturn;
  }

  @Override
  public Return visitStructureIn(final StructureIn expr, final Void arg)
      throws VisitorException {
    // Is the run-class specified by this expression already in the
    // togetherUnder or independantlyUnder stack? If so, this expression is
    // redundant.
    // (e.g. SAME:line(IN:line(a b) c) ~~> SAME:line(a b c) )
    boolean alreadyCovered = false;
    List<String> coveredRunClasses = new ArrayList<String>();
    coveredRunClasses.addAll(this.togetherUnder);
    coveredRunClasses.addAll(this.independantlyUnder);
    for (String runClassUnder : coveredRunClasses) {
      alreadyCovered = runClassUnder.equals(expr.getRunClassName());
      if (!alreadyCovered) {
        try {
          SequenceRelationship rela =
              this.schema.findSeqRelationship(runClassUnder, expr.getRunClassName());
          alreadyCovered = SequenceRelationship.AllContainedBy == rela;
        } catch (SchemaValidationException e) {
          this.vtl.addError(e);
        }
      }
      if (alreadyCovered) {
        // this expression is redundant, prune from the expression tree.
        return expr.getSubExpr().accept(this, null);
      }
    }
    // Add the run-class constraint created by this expression to the
    // togetherUnder stack.
    this.independantlyUnder.add(expr.getRunClassName());
    Return subReturn = expr.getSubExpr().accept(this, null);
    this.independantlyUnder.pop();
    // This expression may be eliminated if expressions in the subtree
    // sufficiently
    // constrain the matched structure.
    coveredRunClasses = new ArrayList<String>();
    coveredRunClasses.addAll(subReturn.togetherOver);
    coveredRunClasses.addAll(subReturn.independantlyOver);
    for (String runClassOver : coveredRunClasses) {
      alreadyCovered = runClassOver.equals(expr.getRunClassName());
      if (!alreadyCovered) {
        try {
          SequenceRelationship rela =
              this.schema.findSeqRelationship(runClassOver, expr.getRunClassName());
          alreadyCovered = SequenceRelationship.AllContainedBy == rela;
        } catch (SchemaValidationException e) {
          this.vtl.addError(e);
        }
      }
      if (alreadyCovered) {
        // this expression is redundant, prune from the expression tree.
        return subReturn;
      }
    }
    Return thisReturn =
        new Return(expr.transform(subReturn.transformed), subReturn.togetherOver,
                   subReturn.independantlyOver);
    thisReturn.independantlyOver.add(expr.getRunClassName());
    return thisReturn;
  }

  @Override
  public Return visitStructurePredExpr(final StructurePredExpr expr, final Void arg)
      throws VisitorException {
    throw VisitorException.requireSubclassImplementation();
  }

  @Override
  public Return visitStructureSame(final StructureSame expr, final Void arg)
      throws VisitorException {
    // This expression is redundant if constraints applied by outer
    // expressions subsume those added by this expression
    if (this.isTogetherUnder(expr.getRunClassName(), this.togetherUnder)) { //
      return expr.getSubExpr().accept(this, null);
    }
    // Add the run-class constraint created by this expression to the
    // togetherUnder stack.
    this.togetherUnder.add(expr.getRunClassName());
    Return subReturn = expr.getSubExpr().accept(this, null);
    this.togetherUnder.pop();
    // This expression may be eliminated if constraints applied by the
    // sub-expression subsume the constraints this expression adds.
    if (this.isTogetherUnder(expr.getRunClassName(), subReturn.togetherOver)) { //
      return subReturn;
    }
    Return thisReturn =
        new Return(expr.transform(subReturn.transformed), subReturn.togetherOver,
                   subReturn.independantlyOver);
    thisReturn.togetherOver.add(expr.getRunClassName());
    return thisReturn;
  }
}
